package com.cat.dataStructure02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-special-integers/description/
 * @create 2025/10/29 18:05
 * @since JDK17
 */
class Solution80 {
    public int countSpecialNumbers(int n) {
        int offset = 1, t = n / 10, len = 1, ans = 0;
        while (t > 0) {
            offset *= 10;
            t /= 10;
            len++;
        }
        int[] cnt = new int[len + 1];
        cnt[0] = 1;
        for (int i = 1, k = 10 - len + 1; i < len; i++, k++) {
            cnt[i] = cnt[i - 1] * k;
        }
        if (len >= 2) { // 比len小的位数
            ans = 9;
            for (int a = 9, b = 9, i = 2; i < len; i++, b--) {
                a *= b;
                ans += a;
            }
        }
        int first = n / offset;
        ans += (first - 1) * cnt[len - 1];
        // 最高位已经被使用
        ans += f(cnt, n, len - 1, offset / 10, 1 << first);
        return ans;
    }

    int f(int[] cnt, int num, int len, int offset, int status) {
        if (len == 0) {
            return 1;
        }
        int ans = 0;
        int first = (num / offset) % 10;
        for (int i = 0; i < first; i++) {
            if ((status & (1 << i)) == 0) {    // 没有被使用过
                ans += cnt[len - 1];    // 畅选
            }
        }
        if ((status & (1 << first)) == 0) {   // 当前位一样大的特殊处理
            ans += f(cnt, num, len - 1, offset / 10, status | (1 << first));
        }
        return ans;
    }
}